#include <iostream>
#include <algorithm>
#include <iterator>
#include <utility>
#include "common.h"
using namespace std;

void quicksort (int*, int*);

int main(int argc, const char *argv[])
{
    const int SIZE = 10;
    int test_array[SIZE];
    generate_n (test_array, SIZE, randsome_number (0, 100));

    copy (test_array, test_array + SIZE, 
                            ostream_iterator<int> (cout, " "));
    cout << endl;

    quicksort (test_array, test_array + SIZE);

    copy (test_array, test_array + SIZE, 
                            ostream_iterator<int> (cout, " "));
    cout << endl;
    
    return 0;
}

void quicksort (int* begin, int* end)
{
    if (begin == end) return;

    int* current = begin;
    int* iterator = end - 1;

    //  partition
    while (1)
    {
        while (*iterator > *current) iterator--;
        if (iterator == current) break;
        swap (*iterator, *current);
        swap (iterator, current);
        iterator++;

        while (*iterator < *current) iterator++;
        if (iterator == current) break;
        swap (*iterator, *current);
        swap (iterator, current);
        iterator--;
    }

    //  recursion
    quicksort (begin, current);
    quicksort (current + 1, end);
}
